package com.zhanghp.class017;

import com.zhanghp.common.TreeNode;

import static com.zhanghp.class017.BinaryTreeTraversalRecursion.Solution.*;

/**
 * 递归序的解释
 * 用递归实现二叉树的三序遍历
 *
 * @author zhanghp
 * @since 2024/2/23 13:36
 */
public class BinaryTreeTraversalRecursion {


    static class Solution {

        // 先序 根左右
        public static void preOrder(TreeNode head) {
            if (head == null) {
                return;
            }
            System.out.println(head.val + " ");
            preOrder(head.left);
            preOrder(head.right);
        }

        // 中序 左根右
        public static void inOrder(TreeNode head) {
            if (head == null) {
                return;
            }
            inOrder(head.left);
            System.out.println(head.val + " ");
            inOrder(head.right);
        }

        // 后序 左右根
        public static void posOrder(TreeNode head) {
            if (head == null) {
                return;
            }
            posOrder(head.left);
            posOrder(head.right);
            System.out.println(head.val + " ");
        }
    }

    // 递归基本样子，用来理解递归序
    public static void f(TreeNode head) {
        if (head == null) {
            return;
        }
        // 1
        f(head.left);
        // 2
        f(head.right);
        // 3
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);
        preOrder(head);
        System.out.println();
        System.out.println("先序遍历递归版");

        inOrder(head);
        System.out.println();
        System.out.println("中序遍历递归版");

        posOrder(head);
        System.out.println();
        System.out.println("后序遍历递归版");

    }

}
